1. Field of the Invention
This invention relates to computer system data storage, and more particularly to an apparatus and method for improving the input/output performance of a redundant storage array system.
2. Description of Related Art
A typical data processing system generally includes one or more storage units connected to at least one central processor unit (CPU). The function of the storage units is to store data and programs which the CPU uses in performing particular data processing tasks. Various types of storage units are used in current computer systems. A typical computer system may include one or more large capacity tape units and/or disk drives (magnetic, optical, or semiconductor).
More recently, highly reliable disk array data storage systems have been introduced to the market. A research group at the University of California, Berkeley, in a paper entitled "A Case for Redundant Arrays of Inexpensive Disks (RAID)", Patterson, et al., Proc. ACM SIGMOD, June 1988, has catalogued a number of different types of disk arrays by defining five architectures under the acronym "RAID" (for Redundant Arrays of Inexpensive Disks).
A RAID 1 architecture involves providing a duplicate set of "mirror" data storage units and keeping a duplicate copy of all data on each pair of data storage units. A number of implementations of RAID 1 architectures have been made, in particular by Tandem Computers Incorporated.
A RAID 2 architecture stores each bit of each word of data, plus Error Detection and Correction (EDC) bits for each word, on separate disk drives. For example, U.S. Pat. No. 4,722,085 to Flora et al. discloses a disk drive memory using a plurality of relatively small, independently operating disk subsystems to function as a large, high capacity disk drive having an unusually high fault tolerance and a very high data transfer bandwidth. A data organizer adds 7 EDC bits (determined using the well-known Hamming code) to each 32-bit data word to provide error detection and error correction capability. The resultant 39-bit word is written, one bit per disk drive, on to 39 disk drives. If one of the 39 disk drives fails, the remaining 38 bits of each stored 39-bit word can be used to reconstruct each 32-bit data word on a word-by-word basis as each data word is read from the disk drives, thereby obtaining fault tolerance.
A RAID 3 architecture is based on the concept that each disk drive storage unit has internal means for detecting a fault or data error. Therefore, it is not necessary to store extra information to detect the location of an error; a simpler form of parity-based error correction can thus be used. In this approach, the contents of all storage units subject to failure are "Exclusive OR'd" (XOR'd) to generate parity information. The resulting parity information is stored in a single redundant storage unit. If a storage unit fails, the data on that unit can be reconstructed by XOR'ing the data from the remaining storage units with the parity information; if desired, the reconstructed data can be stored on a replacement storage unit. Such an arrangement has the advantage over the mirrored disk RAID 1 architecture in that only one additional storage unit is required for "N" storage units. A further aspect of the RAID 3 architecture is that the disk drives are operated in a coupled manner, similar to a RAID 2 system, and a single disk drive is designated as the parity unit. One implementation of a RAID 3 architecture is the Micropolis Corporation Parallel Drive Array, Model 1804 SCSI, which uses four parallel, synchronized disk drives and one redundant parity drive. The failure of one of the four data disk drives can be remedied by the use of the parity bits stored on the parity disk drive. Another example of a RAID 3 system is described in U.S. Pat. No. 4,092,732 to Ouchi.
A RAID 4 architecture uses the same parity error correction concept of the RAID 3 architecture, but improves on the performance of a RAID 3 system with respect to random reading of small files by "uncoupling" the operation of the individual disk drive actuators, and reading and writing a larger minimum amount of data (typically, a disk sector) to each disk (this is also known as block striping). A further aspect of the RAID 4 architecture is that a single storage unit is designated as the parity unit.
A RAID 5 architecture uses the same parity error correction concept of the RAID 4 architecture and independent actuators, but improves on the writing performance of a RAID 4 system by distributing the data and parity information across all of the available disk drives. Typically, "N+1" storage units in a set (also known as a "redundancy group") are divided into a plurality of equally sized address areas referred to as blocks. Each storage unit generally contains the same number of blocks. Blocks from each storage unit in a redundancy group having the same unit address ranges are referred to as "stripes". Each stripe has N blocks of data, plus one parity block on one storage unit containing parity for the remainder of the stripe. Further stripes each have parity block, the parity blocks being distributed on different storage units. Parity updating activity associated with every modification of data in a redundancy group is therefore distributed over the different storage units. No single unit is burdened with all of the parity update activity. For example, in a RAID 5 system comprising 5 disk drives, the parity information for the first stripe of blocks may be written to the fifth drive; the parity information for the second stripe of blocks may be written to the fourth drive; the parity information for the third stripe of blocks may be written to the third drive; etc. The parity block for succeeding stripes typically "precesses" around the disk drives in a helical pattern (although other patterns may be used). Thus, no single disk drive is used for storing all of the parity information, as in the RAID 4 architecture. An example of a RAID 5 system is described in U.S. Pat. No. 4,761,785 to Clark et al.
As in a RAID 4 system, a limitation of a RAID 5 system is that a change in a data block requires a Read-Modify-Write sequence comprising a minimum of four storage unit input/output (I/O) accesses: two Read and two Write operations. That is, the old parity block and old data block must be read and XOR'd, and the resulting sum must then be XOR'd with the new data. Both the data and the parity blocks then must be rewritten to the disk drives. While the two Read operations may be done in parallel, as can the two Write operations, modification of a block of data in a RAID 4 or a RAID 5 system still takes substantially longer than the same operation on a conventional disk. A conventional disk does not require the preliminary Read operation, and thus does have to wait for the disk drives to rotate back to the previous position in order to perform the Write operation. The rotational latency time alone can amount to about 50% of the time required for a typical data modification operation. Further, two disk storage units are involved for the duration of each data modification operation, limiting the throughput of the system as a whole.
Moreover, in the general case a fifth storage unit I/O access occurs: to generate a new data block in the first place, most often an old data block is Read, then modified within the CPU to generate a new data block. However, the storage unit controller must re-read the old data block again in order to compute the new parity block. Only in the case of completely generating a new data block in the CPU and writing such new data over an old data block is this fifth I/O access avoided.
Despite the Write performance penalty of RAID 5-type systems, such systems have become increasingly popular, since they provide high data reliability with a low overhead cost for redundancy, good Read performance, and fair Write performance. However, it would be desirable if the performance of such redundant array data storage subsystems could be improved. In particular, a need exists for providing improved performance in RAID 5 storage subsystems by minimizing the number of storage unit accesses required in such systems.
The present invention provides a solution to these problems.